﻿#pragma once
#include<iostream>
#include<assert.h>
#include<thread>
#include<mutex>
#include<vector>
#include<algorithm>
#include<time.h>
#include<unordered_map>

#ifdef _WIN32
	#include <windows.h>
#else
    //..
#endif

#undef min
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;
// thread cache 和 central cache⾃由链表哈希桶的表⼤⼩
static const size_t NFREELISTS = 208;
// page cache 管理span list哈希表⼤⼩
static const size_t NPAGES = 129;
// ⻚⼤⼩转换偏移, 即⼀⻚定义为2^13,也就是8KB
static const size_t PAGE_SHIFT = 13; 
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux;
#endif
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
		void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE,PAGE_READWRITE);
#else
		// linux下brk mmap等
#endif
		if (ptr == nullptr)
			throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}


static void*& NextObj(void* obj)
{ 
	return *(void**)obj;
}
//管理切分好的对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}
	void* Pop()
	{
		//头删
		assert(_freeList);
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = _freeList;
		end = start;
		for (size_t i = 0; i < n-1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList=nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};
//计算对象大小的对齐映射规则
class SizeClass
{
public:
 // 整体控制在最多10%左右的内碎⽚浪费
 // [1,128] 8byte对⻬ freelist[0,16)
 // [128+1,1024] 16byte对⻬ freelist[16,72)
 // [1024+1,81024] 128byte对⻬ freelist[72,128)
 // [8*1024+1,641024] 1024byte对⻬ freelist[128,184)
 // [64*1024+1,256*1024] 8*1024byte对⻬ freelist[184,208)
	static inline size_t _Roundup(size_t size, size_t alignNum)
	{
		return (size + alignNum - 1) & ~(alignNum - 1);
	}
	// 对⻬⼤⼩计算
	static inline size_t Roundup(size_t size)
	{
		if (size <= 128)
		{
			return _Roundup(size, 8);
		}
		else if (size <= 1024)
		{
			return _Roundup(size, 16);
		}
		else if (size <= 8*1024)
		{
			return _Roundup(size, 128);
		}
		else if (size <= 64*1024)
		{
			return _Roundup(size, 1024);
		}
		else if (size <= 256*1024)
		{
			return _Roundup(size, 8*1024);
		}
		else
		{
			return _Roundup(size, 1 << PAGE_SHIFT);  //大于256KB的内存申请按页对齐
		}
	}
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	// 计算映射的哪⼀个⾃由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {	return _Index(bytes, 3);}
		else if (bytes <= 1024) { return _Index(bytes - 128, 4) + group_array[0]; }
		else if (bytes <= 8*1024) { return _Index(bytes - 1024, 7) + group_array[1] + group_array[0]; }
		else if (bytes <= 64 * 1024) { return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0]; }
		else if (bytes <= 256 * 1024) { return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0]; }
		else {	assert(false);}
		return -1;
	}
	//一次从thread cache中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		int num = MAX_BYTES / size;
		if (num < 2) { num = 2; }
		if (num > 512) { num = 512; }
		return num;
	}
 // 计算⼀次向系统获取⼏个⻚
 // 单个对象 8byte
 // ...
 // 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		
		npage >>= PAGE_SHIFT;
		 if (npage == 0)
			 npage = 1;
		
		return npage;
		
	}
};
//管理多个内存页 
struct Span
{
	PAGE_ID _pageId=0;//起始页号
	size_t _n=0;//页数
	Span* _next=nullptr;
	Span* _prev=nullptr;
	size_t _useCount=0;//切好小块内存 被分配个thread cache的计数
	void* _freeList=nullptr;//自由链表
	bool _isUse = false;        //是否在被使用
	size_t _objSize = 0;
};
//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Insert(Span* pos,Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos!=_head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
private:
	Span* _head;
public:
	std::mutex _mtx;//桶锁
};